FIG. 1 illustrates a general purpose computer 20 that includes a central processing unit 22 that communicates with primary memory (generally Random Access Memory) 24 and secondary memory (generally disk storage) 26 over a system bus 28. Input/Output devices 30, such as keyboards, monitors, printers, or data acquisition cards, are also connected to the system bus 28. The CPU 22 executes one or more computer programs stored in primary memory 24. Most instructions and data in a computer program have a corresponding virtual address. Each virtual address is then translated to a physical address located in primary memory 24. If the required information is not in primary memory 24, then a page fault occurs, and the CPU 24 loads the required information from secondary memory 26 into primary memory 24.
The use of virtual addresses in a computer is a technique commonly referred to as "virtual memory". Practically all computers rely upon virtual memory. Virtual memory allows a computer to execute a program that includes a range of addresses that may exceed the actual memory storage capacity of the computer. Thus, programmers are not restricted by memory-size considerations, and the programs are portable between hardware environments with different memory capacities.
As indicated above, there is a need to translate between a virtual address and a physical address. The virtual address is the address locally used by a program. The physical address specifies the actual physical location of the information in the primary memory 24.
FIG. 2 illustrates the translation operation between a virtual address and a physical address. A computer program 32, stored in primary memory 24, includes a set of instructions, one such instruction is illustrated as element 34 in FIG. 2. The instruction 34 is a command to move ("MOV") to register "R" the contents of memory corresponding to the virtual address "0004734" (36). The numbers are in base 16--Hexadecimal. The virtual address 36 includes a virtual page number "0004" (38), also called a virtual memory page address, that is mapped to a page table 40. The page table 40 includes a set of page table translation entries 42. Each page table translation entry 42 includes a virtual page number 44, a valid bit 46, and a physical page number 48 (also called a physical memory page address). If the valid bit is set (digital one), this indicates that a physical page number 48 exists in primary memory 24 corresponding to the virtual page number 38. If the valid bit is not set, then a page fault occurs and the physical page number 48 must be found in secondary memory 26 by the CPU 22. The physical page number 48 specifies a page of memory in primary memory 24. The terms primary memory 24 and physical memory will be used interchangeably herein.
FIG. 2 illustrates the use of a virtual page number as a virtual address. It will be appreciated by those skilled in the art that the virtual page number can be substituted with an entry that allows the derivation of a virtual address. References in this document to virtual page numbers or virtual memory translation entries are intended to describe any virtual page number system or related scheme used to derive a virtual address.
A complete physical address 50 includes the physical page number 48 and a page offset 52. The page offset 52 specifies the row in the page of memory that the address of interest can be found. The page offset 52 is directly obtained (without translation) from the virtual offset portion 54 of the virtual address 36.
In sum, to obtain a physical address 50 from a virtual address 36, the virtual page number 38 of the virtual address (in this example "0004") is mapped to a page table translation entry 42 found in a page table 40. If the page table translation entry 42 has its valid bit set to one, then there is a corresponding physical page number for the virtual page number. The physical page number (in this example "01FD" Hex) forms a portion of the physical address 50. The other portion of the physical address 50 is a page offset value 52 (in this example "734") that is obtained from the virtual offset portion 54 of the virtual address 36.
FIG. 3 illustrates the correspondence between specified physical pages in a page table 40 and different physical locations in physical memory 24. In the page table 40 of FIG. 3, each entry with its valid bit set to a digital one has a pointer to a location in physical memory 24. For those page table entries that have a valid bit set to a digital zero, a page fault occurs, and a page of memory must be fetched from secondary memory 26 into physical memory 24 and a corresponding modification is then made to the page table 40.
To improve the performance of page tables 40, modern computers include a special cache that keeps track of recently used translations. The recent translations are stored because once a translation for a virtual page number is used, it will probably be used again in the near future. This special address translation cache is referred to as a translation-lookaside buffer, or TLB 60. FIG. 1 and 3 illustrate a TLB 60. In FIG. 3 it can be appreciated that a TLB 60 includes a set of TLB translation entries 62. Typically, a TLB translation entry 62 includes a virtual page number 44, a valid bit 46, and a physical page number 48.
A CPU 22 running a computer program initially compares each virtual page number from the computer program to the entries in the TLB 60. If a match is found (called a hit), the physical page number from the TLB 60 is used to form the physical address 50, in the manner previously described.
A TLB 60 is typically implemented in hardware and therefore has fewer entries than a page table 40. In view of the smaller size of a TLB 60, TLB misses occur frequently. After a TLB miss, the page table 40 is queried to determine the physical address. If the page table 40 has the desired information, that information can be loaded from the page table 40 into the TLB 60.
Since it is much faster to obtain a physical address from a TLB 60 than from a page table 40, there are ongoing efforts to improve the amount of information placed in a TLB 60. One obvious solution is to provide a physically larger TLB 60. Of course, this approach is expensive. Other techniques attempt to maximize the size of memory mapped by a TLB 60 without increasing the number of TLB entries. Such schemes include the use of superpages and partial-subblocking. Many commercial architectures support superpages in one form or another, including the SPARC.TM. chip (Sun Microsystems, Mountain View, Calif.), the Alpha.TM. chip (Digital Equipment Corporation, Maynard, Mass.), and the PowerPC.TM. chip (Motorola Corporation, Schaumberg, Ill.). These schemes share the basic idea of reducing the number of TLB entries 62 needed to map a given region of memory.
Superpages improve TLB performance by using one TLB entry instead of several entries for consecutive base pages that belong to the same process. This approach is somewhat limited because it only applies to a single process that is running on the computer. Large commercial and multi-user systems have many processes that reference the same memory object. For example, heavily used libraries, program text segments, and shared buffer regions may each have a few hundred mappings to a single physical address. This phenomenon is illustrated in FIG. 4.
FIG. 4 illustrates Process.sub.-- i, Process.sub.-- j, and Process.sub.-- k running on a computer system. Each memory address in Process.sub.-- i is identified with a context number (program number), shown as CTX.sub.-- i in FIG. 4, and a virtual address, shown as VA.sub.-- i in the figure. The address (CTX.sub.-- i, VA.sub.-- i) points to a particular physical page number 48 (physical memory page address). Similarly, other memory addresses running in other processes, point to the same physical page number. Specifically, CTX.sub.-- j, VA.sub.-- j of Process.sub.-- j and CTX.sub.-- k, VA.sub.-- k of Process-k point to the same physical page number 48.
FIG. 5 illustrates a TLB 60 corresponding to the operations shown in FIG. 4. Each TLB translation entry 62 (each row of the TLB 60) includes a context identification (CTX), a virtual address (VA), a physical page (PP), and attributes, such as a valid bit and protection bits. Note that the physical page (physical memory page address) PP.sub.-- X appears three times in the TLB 34. That is, (CTX.sub.-- i, VA.sub.-- i), (CTX.sub.-- j, VA.sub.-- j), and (CTX.sub.-- k, VA.sub.-- k) each map to the same physical page PP.sub.-- X. It would be highly desirable to provide a TLB that used a single TLB entry for every virtual address that maps to the same physical page. Such a TLB would greatly expand the information content possessed by a single TLB, since a single entry in the TLB could be used to map multiple virtual addresses.
Typically, each address from the CPU 22 includes a context number (CTX.sub.-- CPU) (from a context register in the CPU) and a virtual address (VA.sub.-- CPU). An address received from the CPU to be translated by the TLB or a page table may be referred to as a translation-request virtual memory translation value.
As shown in FIG. 5, the processing of data in a fully associative TLB 60 is done in parallel. That is, each address from the CPU 22 is simultaneously applied to each value in the TLB 60. A TLB hit is declared if the following is true for some page table entry in the TLB: EQU (CTX.sub.-- CPU=CTX.sub.-- PTE)AND(VA.sub.-- CPU=VA.sub.-- PTE)(Equation 1)
This statement indicates that there is a TLB hit when the context identification from the CPU (CTX.sub.-- CPU) is equivalent to the context identification provided in the TLB (CTX.sub.-- PTE; for example, CTX.sub.-- i in FIG. 5) and the virtual address provided to the TLB from the CPU (VA.sub.-- CPU) is equivalent to the virtual address in the TLB (VA.sub.-- PTE; for example VA.sub.-- i in FIG. 5). FIG. 5 illustrates that CTX.sub.-- CPU is applied to each TLB entry and that a "hit" is identified when a match is found. Known hardware is used to accomplish this operation.
In a set-associative TLB, each address from the CPU 22 is simultaneously applied to each value in the TLB set identified by CTX.sub.-- CPU and VA.sub.-- CPU.
The problem of multiple virtual address entries for the same physical address is not limited to TLBs 60, the same problem is associated with software searches of page tables 40 in primary memory 24. When there are many virtual address translations to the same physical address, the page tables 40 may become unnecessarily large. Consequently, searching these large tables for the desired translation is a time consuming operation. Thus, it would be highly desirable to provide main memory page tables 40 that use a single memory translation entry for every virtual memory page address that maps to the same physical memory page address.